package com.heima.leetcode.practice;

/**
 * @description: leetcode 23 合并K个升序链表
 * @author 勾新杰
 * @version 1.0
 * @date 2024/12/7 11:59
 */
public class E23 {

    /**
     * <h3>方法一：分而治之，自顶向下，递归的</h3>
     * @param lists 链表数组
     * @return 合并后的链表
     */
    public ListNode mergeKLists1(ListNode[] lists) {
        if(lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

    /**
     * 分而治之，自顶向下，递归
     * @param lists 链表数组
     * @param begin 开始下标（包含）
     * @param end 结束下标（包含）
     * @return 合并后的链表
     */
    private ListNode merge(ListNode[] lists, int begin, int end){
        if(begin == end) return lists[begin];
        int median = (begin + end) >> 1;
        ListNode list1 = merge(lists, begin, median);
        ListNode list2 = merge(lists, median + 1, end);
        return mergeTwoList(list1, list2);
    }

    /**
     * <h3>方法二：分而治之，自底向上，迭代的</h3>
     * @param lists 链表数组
     * @return 合并后的链表
     */
    public ListNode mergeKLists2(ListNode[] lists) {
        if (lists.length == 0) return null;
        // 使用迭代的方式进行两两合并，每次合并间隔逐步增大
        for (int width = 1; width < lists.length; width <<= 1) {
            for (int i = 0; i + width < lists.length; i += width << 1) {
                // 合并索引为i和i+width的两个链表，并将结果放回原数组的i位置
                lists[i] = mergeTwoList(lists[i], lists[i + width]);
            }
        }
        // 最终合并后的链表位于lists[0]
        return lists[0];
    }

    /**
     * 合并两个有序链表
     * @param list1 链表1
     * @param list2 链表2
     * @return 合并后的链表
     */
    private ListNode mergeTwoList(ListNode list1, ListNode list2){
        ListNode sentinel = new ListNode(), p = sentinel;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                p.next = list1;
                list1 = list1.next;
            }else{
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }
        if (list1 != null) p.next = list1;
        if (list2 != null) p.next = list2;
        return sentinel.next;
    }
}
